import math
from sys import *

def nearest_neighbor_tsp(cities):
    #选择初始点
    start_city = cities[0]
    path = [start_city]
    path_number = [start_city[2]]
    cities.remove(start_city)
    
    #依次选择最近的点写入路径中
    while cities:
        nearest_city = min(cities, key=lambda city: distance(city, path[-1]))
        path.append(nearest_city)
        path_number.append(nearest_city[2])
        cities.remove(nearest_city)
    return path,path_number

def distance(city1, city2):
    return math.sqrt((city1[0]-city2[0])**2 + (city1[1]-city2[1])**2)

